﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortingAlgorthm.Implementation
{
    public class Quicksort<T> : Algorithm<T>
    {
        public override void Sort(IList<T> list)
        {
            _Sort(list, 0, list.Count);
        }
        public void _Sort(IList<T> list, int start, int end)
        {

            if (end - start <= 1)
                return;

            int partitionPoint = _Partition(list, start, end);
            _Sort(list, start, partitionPoint);
            _Sort(list, partitionPoint, end);
        }

        private int _Partition(IList<T> list, int start, int end)
        {
            T element = list[start];
            end--;
            while (true)
            {
                while (Comparer.Compare(element, list[end]) < 0 && start < end)
                    end--;
                if (start == end)
                    break;
                list[start] = list[end];
                while (Comparer.Compare(element, list[start]) > 0 && start < end)
                    start++;
                if (start == end)
                    break;
                list[end] = list[start];

            }
            list[start] = element;
            return start + 1;
        }
    }
}
